<?php
/**
 * Created by PhpStorm.
 * User: simaguo
 * Date: 2018/6/15
 * Time: 13:06
 */

namespace Simaguo\DS\Lists;


class CircularLinkedList
{
    protected $head;//入口
    protected $length;

    public function __construct()
    {
        $this->head = new Node(null);
        $this->head->next = &$this->head;
        $this->length = 0;
    }

    public function length()
    {
        return $this->length;
    }

    public function insert($index, $elem)
    {
        /*if ($index < 0 || $index > $this->length + 1) {
            return false;
        }*/
        //新节点
        $node = new Node($elem);

        $pre = $this->head;//第0个节点
        for ($i = 1; $i < $index; $i++) {
            $pre = $pre->next;//第$index-1个节点
        }

        if (0 == $this->length) {
            $node->next = &$node;
            $this->head->next = &$node;
        } else {
            $node->next = &$pre->next;
            $pre->next = &$node;
        }
        $this->length++;

        return true;
    }

    public function add($elem)
    {
        return $this->insert($this->length + 1, $elem);
    }

    public function get($index)
    {
        /*if ($index < 0 || $index > $this->length + 1) {
            return false;
        }*/

        $pre = $this->head;//第0个节点
        for ($i = 0; $i < $index; $i++) {
            $pre = $pre->next;//第$index-1个节点
        }

        return $pre->elem;
    }

    /*public function last()
    {
        $head = $this->head;
        if($head->next){
            $node = $head->next;
            while ($node->next !== $this->head->next) {
                $node = $node->next;
            }
            return $node;
        }

        return null;

    }*/

    public function delete($index)
    {
        /*if ($index < 0 || $index > $this->length + 1) {
            return false;
        }*/

        $pre = $this->head;//第0个节点

        for ($i = 1; $i < $index; $i++) {
            $pre = $pre->next;//第$index-1个节点
        }

        $elem = $pre->next->elem;//原值

        $next = &$pre->next->next;//下一节点

        if ($this->head->next === $pre->next) {
            if ($next !== $this->head->next) {
                $this->head->next = $next;
            } else {
                $this->head->next = null;
            }
        }

        $pre->next = $next;

        $this->length--;

        return $elem;
    }

    /**
     * 约瑟夫问题
     * @param int $total
     * @param int $position
     * @return $this|null
     */
    public function josephus($total = 41, $position = 3)
    {
        if ($this->length == 0) {
            //$array=[];开始位;
            for ($i = 1; $i <= $total; $i++) {
                $this->add($i);
            }

            while ($this->length() > 2) {
                $this->delete($position);
                //移动开始位置;
                for ($j = 1; $j < $position; $j++) {
                    $this->head->next = &$this->head->next->next;
                }
                //$array[] = $this->get(1);
            }
            //print_r($array);
            return $this;
        }

        return null;
    }
}